import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Random;

public class HDSbackup {
	private int[] elements;
	private int totalHeapSize;
	private int heapSize;

	private int totalNumbers;
	private int maxValue;

	private File inputFile;
	private File outputFile;

	private int deadSpaceStart;

	private BufferedReader reader;
	private BufferedWriter writer;

	public HDSbackup() {
		totalHeapSize = 3;
		deadSpaceStart = 0;
		heapSize = totalHeapSize;
		elements = new int[totalHeapSize];
		//elements = new int[] { 8, 9, 7, 4, 9 };
		totalNumbers = 25;
		maxValue = 25;

		inputFile = new File("inputNumbers.txt");
		outputFile = new File("outputNumbers.txt");

		//generateNumbers();
		fillElementsArrayWithInitialHeapSize();
		//buildHeap();
		
		writeNumbersToOutputFile();
	}

	private void generateNumbers() {
		FileWriter writer = null;

		try {
			if (!inputFile.exists()) {
				writer = new FileWriter(inputFile);

				Random random = new Random();
				for (int i = totalNumbers - 1; i >= 0; i--) {
					writer.append((int) (random.nextInt(maxValue) + 1) + "\n");
				}
			}
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			if (writer != null) {
				try {
					writer.close();
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}
	}

	private void fillElementsArrayWithInitialHeapSize() {
		try {
			String line = null;
			reader = new BufferedReader(new FileReader(inputFile));
			// Fill the elements array with the initial heapSize
			for (int i = 0; i < totalHeapSize; i++) {
				if ((line = reader.readLine()) != null) {
					elements[i] = Integer.parseInt(line);
				}
			}

		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (NumberFormatException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	private void writeNumbersToOutputFile() {
		System.out.println("Elements size: "+ elements.length);
		
		try {
			int smallest = -1;
			String line = null;
			
			writer = new BufferedWriter(new FileWriter(outputFile));
			
			int i = 0;
			int run = 1;
			while((line = reader.readLine()) != null) {
				
				smallest = removeMin();
				writer.write(smallest +"\n");
				System.out.println("S: "+ smallest);
				
				int nextElement = Integer.parseInt(line);
				if(nextElement >= smallest) {
					add(nextElement);
					// Voeg element toe aan heap
					//elements[0] = nextElement;
					//buildHeap();
					//printArray(elements);
				} else {
					deadSpaceStart++;
					heapSize--;
					
					// Verwijder eerste element
					//elements[0] = elements[heapSize]; // Verplaats het laatste element naar het voren en plaats het eerste element op de deadspace
					//elements[heapSize] = nextElement;
				}
				
				if(heapSize == 0) {
					printArray(elements);
					break;
				}
				System.out.println("Run: "+ run);
			}
			
			writer.flush();
			
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	private void printArray(int[] array) {
		System.out.println("");
		System.out.println("");
		System.out.println("#################################");
		for(int i = 0; i < array.length; i++) {
			System.out.println("> : "+ array[i]);
		}
		System.out.println("#################################");
	}
	
	public int removeMin( ) {
        if( isEmpty( ) ) {
            throw new RuntimeException( "Heap is empty!" );
        }
 
        final int min = elements[ 0 ];
        elements[ 0 ] = elements[ heapSize - 1 ];
        if( heapSize > 0 ) siftDown( 0 );
        return min;
    }
 
    /** Checks if the heap is empty. */
    public boolean isEmpty( ) {
        return heapSize == 0;
    }
 
    /** Adds a new element to the heap and sifts up/down accordingly. */
    public void add( final int value ) {
        if( heapSize -1 == elements.length ) {
            throw new RuntimeException( "Heap is full!" );
        }
 
        elements[ heapSize -1] = value;
        siftUp( heapSize );
       // heapSize++;
    }
 
    /**
     * Sift up to make sure the heap property is not broken.
     * This method is used when a new element is added to the heap 
     * and we need to make sure that it is at the right spot.
     */
    private void siftUp( int index ) {
    	index -= 1;
        if( index > 0 ) {
            final int parent = ( index - 1 ) / 2;
            if( elements[ parent ] > elements[ index ] ) {
                swap( parent, index );
                siftUp( parent );
            }
        }
    }
 
    /** 
     * Sift down to make sure that the heap property is not broken 
     * This method is used when removing the min element, and we need 
     * to make sure that the replacing element is at the right spot.
     */
    private void siftDown( int index ) {
 
        final int leftChild = 2 * index + 1;
        final int rightChild = 2 * index + 2;
 
        // Check if the children are outside the array bounds.
        if( rightChild >= heapSize && leftChild >= heapSize) return;
 
        // Determine the smallest child out of the left and right children.
        final int smallestChild = 
            elements[ rightChild ] > elements[ leftChild ] ? leftChild : rightChild;
 
        if( elements[ index ] > elements[ smallestChild ] ) {
            swap( smallestChild, index );
            siftDown( smallestChild );
        }
    }
 
    /** Helper method for swapping array elements */
    private void swap( int a, int b ) {
        int temp = elements[ a ];
        elements[ a ] = elements[ b ];
        elements[ b ] = temp;
    }
}

/*
 * Given: inputdisk IN, outputdisk OUT, array A with size M subdivided into an
 * internal heap with size H and dead space with size D=M-H
 * 
 * read M elements from IN into A
	buildHeap(A), H=M and D=0
	while IN is not empty
		remove smallest element from heap and write this to OUT
		read next element from IN
		if next >= smallest // next fits into current run
			insert next into heap
		else // next does not fit into current run
			H-- and D++ // decrease heapsize, increase dead space
			insert next into dead space // behind the heap
		if H==0 // heap is empty
			buildHeap(dead space), H=M and D=0
	write the rest of heap to OUT
	buildheap(dead space)
	write rest to OUT
 */